package com.zhugang.week04;

/**
 * @program algorithms
 * @description: sortColors
 * @author: chanzhugang
 * @create: 2022/06/30 10:39
 */
public class SortColors {

    public static void main(String[] args) {
        SortColors sortColors = new SortColors();
        int[] nums = new int[]{2, 0, 2, 1, 1, 0};
        sortColors.sortColors(nums);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    /**
     * 75 颜色分类（原地排序）
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 本质是排序数组从小到大（快排）
        sort_r(nums, 0, nums.length - 1);
    }

    private void sort_r(int[] nums, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = partition(nums, p, r);
        sort_r(nums, p, q - 1);
        sort_r(nums, q + 1, r);
    }

    private int partition(int[] nums, int p, int r) {
        int i = p - 1;
        int j = p;
        while (j < r) {
            if (nums[j] < nums[r]) {
                swap(nums, i + 1, j);
                i++;
            }
            j++;
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}